package suanfa;

import java.util.PriorityQueue;
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class mergeKLists {public ListNode mergeKLists(ListNode[] lists) {
//    //1.方法一优先级队列
//    PriorityQueue<ListNode> heap=new PriorityQueue<>((v1, v2)-> v1.val-v2.val);
//    //2.把所有头节点节点放到小根堆中
//    for(ListNode head:lists){
//        if(head!=null){
//            heap.offer(head);
//        }
//    }
//    //3.合并链表
//    ListNode ret=new ListNode(0);
//    ListNode prev=ret;
//    while(!heap.isEmpty()){
//        ListNode t=heap.poll();
//        prev.next=t;
//        prev=t;
//        if(t.next!=null) heap.offer(t.next);
//    }
//    return ret.next;
    return merge(lists,0,lists.length-1);
}
    public ListNode merge(ListNode[] lists,int left,int right){
        if(left>right) return null;
        if(left==right) return lists[left];
        //1.平分数组
        int mid=(left+right)/2;
        //[left,mid][mid+1,right]
        //2.递归处理左右两部分
        ListNode l1=merge(lists,left,mid);
        ListNode l2=merge(lists,mid+1,right);
        //3.合并两个有序链表
        return mergeTwoList(l1,l2);
    }
    public ListNode mergeTwoList(ListNode l1,ListNode l2){
        if(l1==null) return l2;
        if(l2==null) return l1;
        //合并两个有序链表
        ListNode head=new ListNode(0);
        ListNode cur1=l1,cur2=l2,prev=head;
        while(cur1!=null && cur2!=null){
            if(cur1.val<=cur2.val){
                prev.next=cur1;
                prev=cur1;
                cur1=cur1.next;
            }else{
                prev.next=cur2;
                prev=cur2;
                cur2=cur2.next;
            }
        }
        if(cur1!=null) prev.next=cur1;
        if(cur2!=null) prev.next=cur2;
        //head是一个虚拟的头节点，prev和head指向的都是一个虚拟头节点
        //head是指向头部，head是指向尾部的。
        return head.next;
    }
}
